// Package _3_图的宽度优先遍历 main
// @Title _3_图的宽度优先遍历
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-17 13:29
// @Create  2022-01-17 13:29
package main

import "fmt"

type Edge struct {
	Weight int   // 权重（距离）
	From   *Node // 从哪里来
	To     *Node // 到哪里去
}

type Node struct {
	Val  int     // 实际的数据项
	In   int     // 入度，有多少个点，所发散的边是指向自己的 { 无向图的入度= 出度}
	Out  int     // 出度，自己发散出去多少个边
	Next []*Node // 临接的点集
	Edge []*Edge // 临接的边集
}

type Graph struct {
	Node map[int]*Node   // 点集 编码-> 实际的点
	Edge map[*Edge]*Edge // 边集
}

func BFS(node *Node) {
	if node == nil {
		return
	}
	//创建一个队列
	queue := []*Node{}
	hashSet := make(map[*Node]*Node) // 用来去重，因为图可能有环
	queue = append(queue, node)
	hashSet[node] = node
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		fmt.Println(cur.Val)
		for i := 0; i < len(node.Next); i++ {
			if _, ok := hashSet[node.Next[i]]; !ok {
				hashSet[node.Next[i]] = node.Next[i]
				queue = append(queue, node.Next[i])
			}
		}
	}
}

func main() {

}
